package cn.arnold.treeapplication;

import java.util.Arrays;

public class HeapSort {
    public static void main(String[] args) {
        int[] array = {4, 6, 8, 5, 9};
        sort(array);
        System.out.println(Arrays.toString(array));
    }

    public static void sort(int[] array) {
        int temp = 0;
        // 将无序数组调整为大顶堆进行升序排列
        for (int i = array.length / 2 - 1; i >= 0; i--) {
            adjustHeap(array, i, array.length);
        }
        //1. 将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端
        //2. 重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。
        for (int j = array.length - 1; j > 0; j--) {
            // 交换
            temp = array[j];
            array[j] = array[0];
            array[0] = temp;
            // 将交换后的数列调整为大顶堆
            adjustHeap(array, 0, j);
        }

    }

    /**
     * 将数组调整为大顶堆
     *
     * @param array
     * @param i      非叶子节点对应的数组的索引，i从二叉树的最后一个非叶子节点开始（array.length/2-1）
     * @param length 表示对多少个元素进行调整，length在逐渐减少，第一次为数组的长度
     */
    public static void adjustHeap(int[] array, int i, int length) {
        int temp = array[i];    // 当前元素的值
        // k=i*2+1：表示当前节点的左子节点
        for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
            // 左子节点array[k]和右子节点比较array[k+1]
            if (k + 1 < length && array[k + 1] > array[k]) {
                k++;    // 右子节点大，指向右子节点
            }
            // 此时找到了当前节点的子节点中较大的一个数：指向k，接下来比较较大子节点和父节点
            // 若子节点大于父节点
            if (array[k] > temp) {
                array[i] = array[k];  // 把较大的值赋给当前节点
                i = k;    // !!! i指向k，继续循环比较
            } else {
                break;
            }
        }
        // for循环结束后，已经将以i为父节点的子树调整为大顶堆（局部）
        array[i] = temp;
    }
}
